The invention relates generally to data storage systems, and in particular, to data storage systems in which job scheduling of I/O requests is performed.
The scheduling of I/O requests directed to storage devices in a data storage system is typically performed by a job scheduler in a controller associated with the storage devices. The job scheduler maintains, for each storage device, a list of requests waiting to use the storage device. The order in which jobs are generated for a selected storage device by the job scheduler for such pending I/O requests may vary from the order in which the I/O requests are received by the controller. Typically, the order is determined by the priority of the requests, with preferential scheduling treatment being given to the higher priority requests. Prior scheduling techniques have been designed to either favor the higher priority request 100% of the time that such a higher priority request is pending or reserve fixed time periods in which jobs may be generated for lower priority requests. Because these approaches are somewhat rigid, they tend to starve lower priority background operations over time.
This invention relates to probability-based scheduling of operation requests, such as operation requests directed to devices for job generation.
In an aspect of the invention, a determination is made as to which operations associated with each of a plurality of priority classes have been requested and one of the operations is selected by performing a probability-based operations lookup based on the determination.
Embodiments of the invention may include one or more of the following features.
The probability-based operations lookup may use a table of entries corresponding to different operations. A plurality of first selection values, one corresponding to each of the priority classes in the plurality is formed, and one of the priority classes in the plurality of priority classes, may be selected based on the determination. A corresponding one of the plurality of first selection values corresponding to the selected one of the plurality of priority classes may be selected as a lookup index pointing to one of the entries.
The probability-based operations lookup can include a first lookup level corresponding to a probability-based priority class lookup and a second lookup level corresponding to the probability-based operations lookup. The selection of one of the priority classes in the plurality of priority classes includes deriving a second selection value from the first selection values and using the second selection value as a first lookup index at the first lookup level and using the selected one of the first selection values as an second lookup index at the second lookup level.
Determining which operations associated with each of a plurality of priority classes have been requested may include: associating bitmaps with the priority classes, the bitmaps having bits corresponding to available operation types within the priority classes with which the bitmaps are associated; setting the corresponding bits for requested ones of the available operation types in one or more of the bitmaps to produce corresponding class_mask bitmap values; and producing an operation13 classes bitmap value from the class_mask bitmap values, the operation_classes bitmap value having a bit for each of the priority classes and set bits for any of the priority classes for which ones of the available operation types were requested.
Selecting one of the operations may include selecting one of the priority classes by using the operation classes bitmap value as a pointer to an entry in a class scheduling table having rows of entries, each of the entries being assigned a single one of the priority classes based on predetermined probabilities associated with combinations of the priority classes. Selecting one of the operations may further include selecting one of the operations for the selected priority class by using the corresponding class_mask bitmap value as a pointer to an entry in an operation scheduling table having rows of entries, each of the entries being assigned a single one of the operations based on predetermined probabilities associated with combinations of the operations.
The operation selection may further include generating a job for the selected one of operations. A different one of the operations may be selected if the generated job is determined to be unsuccessful. The selection of a different operation may include clearing the corresponding bit for the selected one of the operations in the associated class_mask bitmap for the selected priority class to produce a modified corresponding class mask bitmap value, thereby removing the selected one of the operations from further consideration. The selection of the different operation may further include producing a new operation_classes bitmap value from the modified corresponding class_mask bitmap value and unmodified ones of the class_mask bitmap values.
The operation selection mechanism of the invention is advantageous in that it provides efficient and direct, code-free table look-up for operation selection. Additionally, the hierarchical nature of the probability tables afford maximum flexibility in configuring system in each job scheduling situation.